package com.yiwenup.leetcode.offer;

import com.yiwenup.leetcode.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
 **/
public class No022 {

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了12.26%的用户
     * 内存消耗：36.3 MB, 在所有 Java 提交中击败了46.31%的用户
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        Map<Integer, ListNode> map = new HashMap<>();
        int i = 0;
        while (head != null) {
            map.put(i++, head);
            head = head.next;
        }
        return map.get(map.size() - k);
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：36.5 MB, 在所有 Java 提交中击败了5.14%的用户
     */
    public ListNode getKthFromEnd2(ListNode head, int k) {
        if (head == null || k < 0) return null;
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k; i++) {
            if (fast == null) return null;
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：36.3 MB, 在所有 Java 提交中击败了30.64%的用户
     */
    public ListNode getKthFromEnd3(ListNode head, int k) {
        ListNode counter = head;
        int tmp = 1;
        while (counter != null) {
            counter = counter.next;
            tmp++;
        }
        tmp = tmp - k;

        while (tmp > 0 && head != null) {
            head = head.next;
            tmp--;
        }

        return head;
    }
}
